// https://www.lintcode.com/problem/437/

// class Solution {
// public:
//     /**
//      * @param pages: an array of integers
//      * @param k: An integer
//      * @return: an integer
//      */
//     int copyBooks(vector<int> &pages, int k) {
//         int n = pages.size();
//         vector<vector<int>> ans(k + 1, vector<int>(n + 1, INT_MAX)); // 前k个人抄n本书
//         for (int i = 0; i <= k; ++i) {
//             ans[i][0] = 0;
//         }
//         for (int i = 1; i <= k; ++i) {
//             for (int j = 1; j <= n; ++j) {
//                 int sum = 0;
//                 for (int t = j; t >= 0; --t) {
//                     ans[i][j] = min(ans[i][j], max(ans[i - 1][t], sum));
//                     if (t > 0) sum += pages[t - 1];
//                 }
//             }
//         }
//         return ans[k][n];
//     }
// };

// 法二：二分法二分答案，限定时间，每个人分到不能再抄为止
class Solution {
public:
    /**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */

    bool getAns(int time, vector<int> &pages, int k) { 
        //最慢抄书人花费time时间下，k个人够不够
        int tmp = pages[0]; //当前的人用的时间
        int num = 1; //当前人数
        for (int i = 1; i < pages.size(); ++i) {
            if (tmp + pages[i] > time) { 
                tmp = 0;
                num++;
            } 
            tmp += pages[i];
        }
        return num <= k;
    }

    int copyBooks(vector<int> &pages, int k) {
        if (pages.empty()) return 0;
        int low = 0;
        int high = 0;
        for (int page: pages) {
            high += page;
            if (page > low) {
                low = page;
            }
        }
        while (low + 1 < high) {
            int mid = (high - low) / 2 + low;
            if (getAns(mid, pages, k)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        if (getAns(low, pages, k)) {
            return low;
        } else {
            return high;
        }
    }
};